//给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。 
//
// 注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：21
// 
//
// 示例 2： 
//
// 
//输入：n = 21
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
//
// Related Topics 数学 双指针 字符串 👍 304 👎 0


package leetcode.editor.cn;

/**
 * 下一个更大元素 III
 * @date 2022-10-10 09:00:28
 */
class P556_NextGreaterElementIii{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P556_NextGreaterElementIii().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int nextGreaterElement(int n) {
		//1 将n转换为字符数字
		String s = String.valueOf(n);
		char[] chars = s.toCharArray();
		int pos = -1;
		for (int i = chars.length-1; i >= 0; i--) {
			if(i > 0 && chars[i-1] < chars[i]){
				pos = i-1;
				break;
			}
		}
		//没有合乎条件的pos
		if(pos == -1){
			return -1;
		}
		//找到第一个大于pos的值进行交换
		for (int i = chars.length-1; i >= 0; i--) {
			if(chars[i] > chars[pos]){
				swap(chars,pos,i);
				break;
			}
		}
		//将pos后的序列进行反转
		int j = pos + 1,k = chars.length-1;
		while(j < k){
			swap(chars,j,k);
			j++;
			k--;
		}
		//判断交换后是否越界
		long ans = Long.parseLong(String.valueOf(chars));
		return ans > Integer.MAX_VALUE ?-1 : (int)ans;
    }
	public void swap(char[] chars,int i,int j){
		char temp = chars[i];
		chars[i] = chars[j];
		chars[j] = temp;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
